lib/Mi manual de algoritmos/version_world_finals_2009/src/geometria/is_inside_concave_polygon.cpp

   1 //Point
   2 //Choose one of these two:
   3 struct P {
   4   double x, y; P(){}; P(double q, double w) : x(q), y(w){}
   5 };
   6 struct P {
   7   int x, y; P(){}; P(int q, int w) : x(q), y(w){}
   8 };
   9
  10 // Polar angle
  11 // Returns an angle in the range [0, 2*Pi) of a given Cartesian point.
  12 // If the point is (0,0), -1.0 is returned.
  13 // REQUIRES:
  14 // include math.h
  15 // define EPS 0.000000001, or your choice
  16 // P has members x and y.
  17 double polarAngle( P p )
  18 {
  19   if(fabs(p.x) <= EPS && fabs(p.y) <= EPS) return -1.0;
  20   if(fabs(p.x) <= EPS) return (p.y > EPS ? 1.0 : 3.0) * acos(0);
  21   double theta = atan(1.0 * p.y / p.x);
  22   if(p.x > EPS) return(p.y >= -EPS ? theta : (4*acos(0) + theta));
  23   return(2 * acos( 0 ) + theta);
  24 }
  25
  26 //Point inside polygon
  27 // Returns true iff p is inside poly.
  28 // PRE: The vertices of poly are ordered (either clockwise or
  29 //      counter-clockwise.
  30 // POST: Modify code inside to handle the special case of "on
  31 // an edge".
  32 // REQUIRES:
  33 // polarAngle()
  34 // include math.h
  35 // include vector
  36 // define EPS 0.000000001, or your choice
  37 bool pointInPoly( P p, vector< P > &poly )
  38 {
  39   int n = poly.size();
  40   double ang = 0.0;
  41   for(int i = n - 1, j = 0; j < n; i = j++){
  42     P v( poly[i].x - p.x, poly[i].y - p.y );
  43     P w( poly[j].x - p.x, poly[j].y - p.y );
  44     double va = polarAngle(v);
  45     double wa = polarAngle(w);
  46     double xx = wa - va;
  47     if(va < -0.5 || wa < -0.5 || fabs(fabs(xx)-2*acos(0)) < EPS){
  48         // POINT IS ON THE EDGE
  49         assert( false );
  50         ang += 2 * acos( 0 );
  51         continue;
  52       }
  53     if( xx < -2 * acos( 0 ) ) ang += xx + 4 * acos( 0 );
  54     else if( xx > 2 * acos( 0 ) ) ang += xx - 4 * acos( 0 );
  55     else ang += xx;
  56   }
  57   return( ang * ang > 1.0 );
  58 }